package top.datacluster.basic.structure.tree;

/**
 * 二叉堆，通过数组的方式实现二叉堆，根节点在数组1的位置。
 * @param <T>
 */
public class MinBinaryHeap<T extends Comparable> {

    private Object[] elements;

    private int size = 15;

    private int count = 0;

    public MinBinaryHeap(int size) {
        elements = new Object[size];
        this.size = size;
    }

    public MinBinaryHeap() {
        elements = new Object[size];
    }

    public boolean insert(T element) {
        if (isEmpty()){
            this.elements[1] = element;
            count++;
        }else{
            //插入的位置等于当前的数量+1
            int index = count + 1;
            int parnetIndex = getParent(index);
            this.elements[index] = element;
            count++;
            while (parnetIndex !=0 && ((T)this.elements[parnetIndex]).compareTo(element) > 0){
                Object temp = this.elements[parnetIndex];
                this.elements[parnetIndex] = element;
                this.elements[index] = temp;
                index = parnetIndex;
                parnetIndex = getParent(index);
            }

        }
        return true;
    }


    private int getParent(int index){
        return index / 2;
    }

    /**
     * 对二叉堆进行扩容
     */
    public void resize(){
        int oldSize = this.size;
        int newSize = oldSize / 2;
        T[] newArray = (T[]) new Object[oldSize + newSize];
        for (int i = 1; i < count; i++){
            newArray[i] = (T) this.elements[i];
        }

        this.elements = newArray;
    }

    public void print(){
        for (int i = 1; i < count + 1; i++){
            System.out.print(this.elements[i] + "\t");
        }
    }

    public boolean isEmpty(){
        return count == 0;
    }

    public int getLeft(int index){
        return index * 2;
    }

    public int getRight(int index){
        return index * 2 + 1;
    }

    public T getIndex(int index){
        return (T) this.elements[index];
    }

    public static void main(String[] args) {
        Integer[] test = new Integer[]{ 23, 43, 12, 54, 41, 35};
        MinBinaryHeap<Integer> minBinaryHeap = new MinBinaryHeap<Integer>();
        for (Integer i : test){
            minBinaryHeap.insert(i);
        }
        minBinaryHeap.print();
    }
}
